/*
在用除余法作为散列函数、线性探测解决冲突的散列表中，写一删除关键字的算法，要求将所有可以前移的元素前移去填充被删除的空位，以保证探测序列不致于断裂。

【输入形式】

    三行，

      第一行是键盘先输入一个整数m，表示哈希表的长度，

      利用m求p的值（小于等于m的最大的素数）；

      第二行是连续输入多个整数（以0作为结束）；

      第三行是输入要删除的关键字；

【输出形式】

      如果没有要删除的关键字，输出“No”，并输出相应的哈希表

      如果有要删除的关键字，输出删除关键字后的哈希表。

     （关键字之间空2个空格）

样例1

输入：

10

30 15 21 40 25 26 36 37 0

36

输出：

建立的哈希表如下：

0  1  2  3  4  5  6  7  8  9  

21  15  30  36  25  40  26  37  -1  -1  

删除关键字36后的哈希表如下：

0  1  2  3  4  5  6  7  8  9  

21  15  30  37  25  40  26  -1  -1  -1  



样例2

输入：

10

30 15 21 40 25 26 36 37 0

24

输出：

建立的哈希表如下：

0  1  2  3  4  5  6  7  8  9  

21  15  30  36  25  40  26  37  -1  -1  

No

删除关键字24后的哈希表如下：

0  1  2  3  4  5  6  7  8  9  

21  15  30  36  25  40  26  37  -1  -1  
*/

#include <iostream>
#include <stack>
#include <queue>
#define maxsize 1000
using namespace std;
typedef struct
{
    int key;//关键字
    int count;//比较次数
}Hash[maxsize];
void creatHash(Hash H, int m, int mod);
void cinHash(Hash H, int m, int mod, int k);
int maxsu(int m); // 小于等于m的最大素数
int prime(int n); // 判断素数
int k[maxsize];
int prime(int n)//判断素数
{
    
    int i;
    for(i=2;i<n;i++)
    {
        if(n%i==0)
        {
            return 0;
        }
    }
    return 1;
}

int maxsu(int m)//小于等于m的最大素数
{
    int i, su;
    i = 2;
    su = 2;
    while(i<=m)
    {
        if(prime(i)==1)
        {
            su = i;
        }
        i++;
    }
    return su;
}
void cinHash(Hash H, int m,int mod, int k)
{
    int h;//散列地址
    int i, hi;
    h = k % mod; // 哈希函数H(k)=k%13
    if(H[h].key == -1)//不冲突，直接入表
    {
        H[h].key = k;//入散列表
        H[h].count = 1;//比较次数
    } 
    else
    {
        i = 0;
        do{
            h++;
            hi = h % m;//线性探测法解决冲突
            i++;//比较次数
        } while (H[hi].key != -1);
        H[hi].key = k;
        H[hi].count = i;
    }
}

void creatHash(Hash H,int m,int mod)
{
    int i;
    for (i = 0; i < m; i++)//初始化哈希表
    {
        H[i].key = -1;
        H[i].count = 0;
    }
    int j = 0;
    cin >> k[j];
    while (k[j] != 0)
    {
        cinHash(H, m, mod, k[j]);
        j++;
        cin >> k[j];
    }
}

int main()
{
    int i, j, m, mod, del;
    Hash H;
    cin >> m;
    mod = maxsu(m);
    creatHash(H, m, mod);//建立哈希表
    cout << "建立的哈希表如下：" << endl;
    for (i = 0; i < m; i++)
        cout << i << "  ";
    cout << endl;
    for (i = 0; i < m; i++)
        cout << H[i].key << "  ";//输出初始元素建立的哈希表
    cout << endl;
    cin >> del;//输入要删除的关键字
    for (i = 0; i < m; i++)//初始化哈希表，为重新建立哈希表做准备
    {
        H[i].key = -1;
        H[i].count = 0;
    }
    j = 0;
    i = 0;
    while (k[j] != 0)
    {//所有的元素都按初始输入顺序存在属数组k[]里，结尾标志为k[]=0
        if(k[j]==del)//待删除元素和初始元素比较
        {
            i = 1;//i作为标识符判断待删除关键字是否存在
        }
        else//不是要删除的元素拿去建立散列表
        {
            cinHash(H, m, mod, k[j]);
        }
        j++;
    }
    if(!i)
    {
        cout << "No" << endl;
    }
    cout << "删除关键字" << del << "后的哈希表如下：" << endl;
    for (i = 0; i < m; i++)
        cout << i << "  ";
    cout << endl;
    for (i = 0; i < m; i++)
        cout << H[i].key << "  ";
    return 0;

}
